package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/09/28 21:22
 **/
public class Day27_2_Num264_NthUglyNumber {
    class Solution {
        public int nthUglyNumber(int n) {
            int[] dp = new int[n];
            int ind2 = 2, ind3 = 3, ind5 = 5;
            int res;
            dp[0] = 1;
            for(int i = 1; i < n; ++i){
                res = Math.min(dp[ind2] * 2, Math.min(dp[ind3] * 3, dp[ind5] * 5));
                if(res % 2 == 0) ind2++;
                if(res % 3 == 0) ind3++;
                if(res % 5 == 0) ind5++;
                dp[i] = res;
            }
            return dp[n-1];
        }
    }
}